.SEC(Applications and Examples of LISP definitions,Applications and Examples)
.BEGIN INDENT 20,20;
"...All the time I design programs for nonexiting machines and add:
`if we now had a machine comprising the primitives here assumed, then the job is
done.'

 ... In actual practice, of course, this ideal machine will turn out not to exist, so
our next task --structurally similar to the original one-- is to program the
simulation of the "upper" machine.... But this bunch of programs is written
for a machine that in all probability will not exist, so our next job will be
to simulate it in terms of programs for a next lower level machine, etc.,
until finally we have a program that can be executed by our hardware...."
.END
.BEGIN TURN ON "←";

←E. W. Dijkstra, %3Notes on Structured Programming%1
.END

.BEGIN TURN ON "←";
.SS(Examples of Definitions)
We have already seen a few examples of definition and evaluation of
non-primitive LISP functions.  This section will spend a good deal of
time showing different styles of definition, giving hints about how to
write LISP functions, and increase your familiarity with LISP. Finally,
 several complete and non-trivial examples will be  described as LISP
functions.

The style of definition available in our current subset of LISP is
%2⊗→definition by recursion↔←%*. That is, a typical LISP definition
will contain applications of that function name being defined.
Consider the factorial function, n!. We might characterize this function
by saying:

%21.%*  The function is defined for non-negative integers.

%22.%*  The value of the function for 0 is 1.

%23%*.  Otherwise the value of n! is n times the value of n-1!.

The implication here is that it is somehow easier to compute n-1! than
to compute n!. 

Recall also our example of %3equal%* on {yon(P1)}. The question
of equality for two non-atomic sexprs was thrown back to the
question of equality for their %3car%*s and %3cdr%*s. 

These examples are typical of LISP definitions.
The body of the definiton is a conditional expression
first involving a few special cases, called %2⊗→termination conditions↔←%*.
Then, the remainder of the conditional covers the general case-- what to
do if the argument to the function is not one of the special cases.
The termination case for the factorial should be: "is the argument 0?"
⊗↓What we obviously means is "is the %2value%* of the argument %30%*?".
Unless we desire precision, we will frequently misuse the language this way←;
termination for %3equal%* involves: "are either of the arguments atomic?".

It should now be clear how to write a LISP program for the factorial function:

.BEGIN CENTERIT;SELECT 3;
.P20:
←fact[n] <= [eq[n;0] → 1; T → times[n;fact[n-1]]] ⊗↓%3times%1 is assumed
to be a LISP function  which performs multiplication.  %3n-1%* should actually
be written: %3sub1[n]%*, where the function %3sub1%* does what you think it does.←

.END
Notice that %3fact%* is a partial function, defined only for non-negative
integer. %3equal%* is a total predicate; it is defined for all arguments.

When writing or reading LISP definitions pay particular attention to the
domain of definition. The following general hints should be useful:

%21%*.  Is it a function or predicate?

%22%*.  Are there any restrictions on the argument positions?

%23%*.  Are the termination conditions compatible with the restrictions
on the arguments?  If it is a recursion on lists, check for the empty
list; if it is a recursion of arbitrary sexprs, then check for the
appearance of an atom.

%24%*.  Whenever a function call is made within the definition are all
the restrictions on that function satisfied?

%25%*.  Don't try to do too much. Be lazy. There is usually a very simple
termination case. 
If the termination case looks messy there is probably something wrong with your
conception of the program.
If the gereral case looks messy, then write some  subfunctions
to perform the brunt of the calculation. 

Use the above  suggestions when writing any subfunction. When you are
finished, no function will do very much, but the net effect of all the
functions acting in concert is a solution to your problem. That is
part of the mystery of recursive programming.


Here are some more examples of LISP definitions.